home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 3 / Cream of the Crop 3.iso / comm / wnos5src.zip / IPROUTE.C < prev    next >
Text File  |  1993-08-09  |  16KB  |  600 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include "global.h"
  5. #include "mbuf.h"
  6. #include "iface.h"
  7. #include "timer.h"
  8. #include "internet.h"
  9. #include "ip.h"
  10. #include "netuser.h"
  11. #include "icmp.h"
  12. #include "trace.h"
  13. #include "pktdrvr.h"
  14. #include "files.h"
  15.  
  16. #define    RIP_INFINITY    16
  17.  
  18. struct route *Routes = NULLROUTE;        /* Routing table */
  19.  
  20. struct route R_default = {                /* Default route entry */
  21.     NULLROUTE,
  22.     0,
  23.     0,
  24.     0,
  25.     RIP_INFINITY,
  26.     NULLIF,
  27.     0,
  28.     0,
  29.     0
  30. };
  31.  
  32. int32 Ip_addr;
  33.  
  34. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  35.  * coming or going, must pass.
  36.  *
  37.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  38.  * broadcast. The router will kick the packet upstairs regardless of the
  39.  * IP destination address.
  40.  */
  41. int
  42. ip_route(
  43. struct iface *i_iface,            /* Input interface */
  44. struct iface *r_iface,            /* Routing interface */
  45. struct mbuf *bp,                /* Input packet */
  46. int rxbroadcast)                /* True if packet had link broadcast address */
  47. {
  48.     struct ip ip;                /* IP header being processed */
  49.     int16 ip_len;                /* IP header length */
  50.     int16 length;                /* Length of data portion */
  51.     int32 gateway;                /* Gateway IP address */
  52.     struct route *rp;            /* Route table entry */
  53.     struct iface *iface;        /* Output interface, possibly forwarded */
  54.     int16 offset;                /* Offset into current fragment */
  55.     int16 mf_flag;                /* Original datagram MF flag */
  56.     int strict = 0;                /* Strict source routing flag */
  57.     char prec;                    /* Extracted from tos field */
  58.     char del;
  59.     char tput;
  60.     char rel;
  61.     int16 opt_len;                /* Length of current option */
  62.     char *opt;                    /* -> beginning of current option */
  63.     char *ptr;                    /* -> pointer field in source route fields */
  64.     struct mbuf *tbp;
  65.     int ckgood = 1;
  66.  
  67.     if(i_iface != NULLIF){
  68.         ipInReceives++;            /* Not locally generated */
  69.         i_iface->iprecvcnt++;
  70.     }
  71.     if(len_p(bp) < IPLEN){
  72.         /* The packet is shorter than a legal IP header */
  73.         ipInHdrErrors++;
  74.         free_p(bp);
  75.         return -1;
  76.     }
  77.     /* Sneak a peek at the IP header's IHL field to find its length */
  78.     if((ip_len = (bp->data[0] & 0xf) << 2) < IPLEN) {
  79.         /* The IP header length field is too small */
  80.         ipInHdrErrors++;
  81.         free_p(bp);
  82.         return -1;
  83.     }
  84.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  85.         /* Bad IP header checksum; discard */
  86.         ipInHdrErrors++;
  87.         free_p(bp);
  88.         return -1;
  89.     }
  90.     /* Extract IP header */
  91.     ntohip(&ip,&bp);
  92.  
  93.     if(ip.version != IPVERSION){
  94.         /* We can't handle this version of IP */
  95.         ipInHdrErrors++;
  96.         free_p(bp);
  97.         return -1;
  98.     }
  99.  
  100.     /* Trim data segment if necessary. */
  101.     length = ip.length - ip_len;    /* Length of data portion */
  102.     trim_mbuf(&bp,length);
  103.  
  104.     /* If we're running low on memory, return a source quench */
  105.     if((rxbroadcast == 0) && (availmem() == 0))
  106.         icmp_output(&ip,bp,ICMP_QUENCH,0,NULLICMP);
  107.  
  108.     /* Process options, if any. Also compute length of secondary IP
  109.      * header in case fragmentation is needed later
  110.      */
  111.     strict = 0;
  112.     for(opt = ip.options; opt < &ip.options[ip.optlen]; opt += opt_len) {
  113.         /* Most options have a length field. If this is a EOL or NOOP,
  114.          * this (garbage) value won't be used
  115.          */
  116.         opt_len = uchar(opt[1]);
  117.  
  118.         switch(opt[0] & OPT_NUMBER){
  119.         case IP_EOL:
  120.             goto no_opt;        /* End of options list, we're done */
  121.         case IP_NOOP:
  122.             opt_len = 1;
  123.             break;                /* No operation, skip to next option */
  124.         case IP_SSROUTE:        /* Strict source route & record route */
  125.             strict = 1;            /* note fall-thru */
  126.         case IP_LSROUTE:        /* Loose source route & record route */
  127.             /* Source routes are ignored unless we're in the
  128.              * destination field
  129.              */
  130.             if(ismyaddr(ip.dest) == NULLIF)
  131.                 break;            /* Skip to next option */
  132.             if(uchar(opt[2]) >= opt_len){
  133.                 break;            /* Route exhausted; it's for us */
  134.             }
  135.             /* Put address for next hop into destination field,
  136.              * put our address into the route field, and bump
  137.              * the pointer
  138.              */
  139.             ptr = opt + uchar(opt[2]) - 1;
  140.             ip.dest = get32(ptr);
  141.             put32(ptr,locaddr(ip.dest));
  142.             opt[2] += 4;
  143.             ckgood = 0;
  144.             break;
  145.         case IP_RROUTE:
  146.             /* Record route */
  147.             if(uchar(opt[2]) > opt_len - 3){
  148.                 /* Route area exhausted; kick back an error */
  149.                 if(!rxbroadcast){
  150.                     union icmp_args icmp_args;
  151.  
  152.                     icmp_args.pointer = IPLEN + opt - ip.options;
  153.                     icmp_output(&ip,bp,ICMP_PARAM_PROB,0,&icmp_args);
  154.                 }
  155.                 free_p(bp);
  156.                 return -1;
  157.             }
  158.             /* Add our address to the route */
  159.             ptr = opt + uchar(opt[2]) - 1;
  160.             ptr = put32(ptr,locaddr(ip.dest));
  161.             opt[2] += 4;
  162.             ckgood = 0;
  163.             break;
  164.         }
  165.     }
  166. no_opt:
  167.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  168.     if(ismyaddr(ip.dest) != NULLIF || rxbroadcast) {
  169.         if(r_iface != NULLIF) {
  170.             rt_add(ip.source,32,0,r_iface,8,1200,3);
  171.         }
  172. #ifdef    GWONLY
  173.     /* We're only a gateway, we have no host level protocols */
  174.         if(!rxbroadcast) {
  175.             icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_PROT_UNREACH,NULLICMP);
  176.         }
  177.         ipInUnknownProtos++;
  178.         free_p(bp);
  179. #else
  180.         ip_recv(i_iface,&ip,bp,rxbroadcast);
  181. #endif
  182.         return 0;
  183.     }
  184.     /* Packet is not destined to us. If it originated elsewhere, count
  185.      * it as a forwarded datagram.
  186.      */
  187.     if(i_iface != NULLIF) {
  188.         ipForwDatagrams++;
  189.     }
  190.     /* Adjust the header checksum to allow for the modified TTL */
  191.     ip.checksum += 0x100;
  192.  
  193.     if((ip.checksum & 0xff00) == 0) {
  194.         ip.checksum++;    /* end-around carry */
  195.     }
  196.     /* Decrement TTL and discard if zero. We don't have to check
  197.      * rxbroadcast here because it's already been checked
  198.      */
  199.     if(--ip.ttl == 0){
  200.         /* Send ICMP "Time Exceeded" message */
  201.         icmp_output(&ip,bp,ICMP_TIME_EXCEED,0,NULLICMP);
  202.         ipInHdrErrors++;
  203.         free_p(bp);
  204.         return -1;
  205.     }
  206.     /* Look up target address in routing table */
  207.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  208.         /* No route exists, return unreachable message (we already
  209.          * know this can't be a broadcast)
  210.          */
  211.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  212.         free_p(bp);
  213.         ipOutNoRoutes++;
  214.         return -1;
  215.     }
  216.     rp->uses++;
  217.  
  218.     /* Check for output forwarding and divert if necessary */
  219.     iface = rp->iface;
  220.     if(iface->forw != NULLIF)
  221.         iface = iface->forw;
  222.  
  223.     /* Find gateway; zero gateway in routing table means "send direct" */
  224.     gateway = (rp->gateway == 0) ? ip.dest : rp->gateway;
  225.  
  226.     if(strict && gateway != ip.dest) {
  227.         /* Strict source routing requires a direct entry
  228.          * Again, we know this isn't a broadcast
  229.          */
  230.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_ROUTE_FAIL,NULLICMP);
  231.         free_p(bp);
  232.         ipOutNoRoutes++;
  233.         return -1;
  234.     }
  235.     prec = PREC(ip.tos);
  236.     del  = ip.tos & DELAY;
  237.     tput = ip.tos & THRUPUT;
  238.     rel  = ip.tos & RELIABILITY;
  239.  
  240.     if(ip.length <= iface->mtu) {
  241.         /* Datagram smaller than interface MTU; put header
  242.          * back on and send normally. Recompute header checksum
  243.          * because we modified the TTL.
  244.          */
  245.         iface->ipsndcnt++;
  246.         tbp = htonip(&ip,bp,ckgood);
  247.         return (*iface->send)(tbp,iface,gateway,prec,del,tput,rel);
  248.     }
  249.     /* Fragmentation needed */
  250.     if(ip.flags.df){
  251.         /* Don't Fragment set; return ICMP message and drop */
  252.         union icmp_args icmp_args;
  253.  
  254.         icmp_args.mtu = iface->mtu;
  255.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_FRAG_NEEDED,&icmp_args);
  256.         free_p(bp);
  257.         ipFragFails++;
  258.         return -1;
  259.     }
  260.     /* Create fragments */
  261.     offset = ip.offset;
  262.     mf_flag = ip.flags.mf;        /* Save original MF flag */
  263.  
  264.     while(length != 0) {        /* As long as there's data left */
  265.         int16 fragsize;            /* Size of this fragment's data */
  266.         struct mbuf *f_data;    /* Data portion of fragment */
  267.  
  268.         /* After the first fragment, should remove those
  269.          * options that aren't supposed to be copied on fragmentation
  270.          */
  271.         ip.offset = offset;
  272.  
  273.         if(length + ip_len <= iface->mtu) {
  274.             /* Last fragment; send all that remains */
  275.             fragsize = length;
  276.             ip.flags.mf = mf_flag;    /* Pass original MF flag */
  277.         } else {
  278.             /* More to come, so send multiple of 8 bytes */
  279.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  280.             ip.flags.mf = 1;
  281.         }
  282.         ip.length = fragsize + ip_len;
  283.  
  284.         /* Duplicate the fragment */
  285.         if((dup_p(&f_data,bp,offset,fragsize)) != fragsize)
  286.             goto quit;
  287.  
  288.         /* Put IP header back on, recomputing checksum and ship it out */
  289.         tbp = htonip(&ip,f_data,0);
  290.  
  291.         if((*iface->send)(tbp,iface,gateway,prec,del,tput,rel) == -1)
  292.             goto quit;
  293.  
  294.         iface->ipsndcnt++;
  295.         ipFragCreates++;
  296.         offset += fragsize;
  297.         length -= fragsize;
  298.     }
  299.     ipFragOKs++;
  300.     free_p(bp);
  301.     return 0;
  302. quit:
  303.     ipFragFails++;
  304.     free_p(bp);
  305.     return -1;
  306. }
  307.  
  308. int
  309. ip_encap(struct mbuf *bp,struct iface *iface,int32 gateway,int prec,int del,int tput,int rel)
  310. {
  311.     struct ip ip;
  312.  
  313.     dump(iface,IF_TRACE_OUT,CL_NONE,bp);
  314.  
  315.     if(gateway == 0L) {
  316.         /* Gateway must be specified */
  317.         ntohip(&ip,&bp);
  318.         icmp_output(&ip,bp,ICMP_DEST_UNREACH,ICMP_HOST_UNREACH,NULLICMP);
  319.         free_p(bp);
  320.         ipOutNoRoutes++;
  321.         return -1;
  322.     }
  323.     /* Encapsulate in an IP packet from us to the gateway */
  324.     return ip_send(INADDR_ANY,gateway,IP_PTCL,0,0,bp,0,0,0);
  325. }
  326.  
  327. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  328. struct route *
  329. rt_add(
  330. int32 target,            /* Target IP address prefix */
  331. unsigned int bits,        /* Size of target address prefix in bits (0-32) */
  332. int32 gateway,            /* Optional gateway to be reached via interface */
  333. struct iface *iface,    /* Interface to which packet is to be routed */
  334. int32 metric,            /* Metric for this route entry */
  335. int32 ttl,                /* Lifetime of this route entry in sec */
  336. char private)            /* Inhibit advertising this entry ? */
  337. {
  338.     struct route *rp, *rptmp;
  339.     int32 gwtmp;
  340.  
  341.     if(iface == NULLIF || (bits == 32 && ismyaddr(target))) {
  342.         return NULLROUTE;    /* Don't accept routes to ourselves */
  343.     }
  344.     /* Encapsulated routes must specify gateway, and it can't be ourselves */
  345.     if(iface == &Encap && (gateway == 0 || ismyaddr(gateway))) {
  346.         return NULLROUTE;
  347.     }
  348.     if(bits > 32) {
  349.         bits = 32;
  350.     }
  351.     target &= (~0L << (32 - bits));
  352.  
  353.     /* Zero bits refers to the default route */
  354.     if((rp = (bits == 0) ? &R_default : rt_blookup(target,bits)) == NULLROUTE) {
  355.         /* The target is not already in the table, so create a new
  356.          * entry and put it in.
  357.          */
  358.         rp = mxallocw(sizeof(struct route));
  359.         rp->metric = RIP_INFINITY;
  360.         rp->next = Routes;
  361.         Routes = rp;
  362.     }
  363.     rp->iface = iface;
  364.  
  365.     if(rp->flags == RTPRIVATE
  366.       || rp->gateway
  367.       || rp->metric < metric
  368.       || rp == &R_default) {
  369.         /* do nothing, used only for faster comparison */
  370.         ;
  371.     } else {
  372.         rp->target = target;
  373.         rp->bits = bits;
  374.         rp->gateway = gateway;
  375.         rp->metric = metric;
  376.  
  377.         if(private != 3) {
  378.             /* Should anyone be told of this route? */
  379.             rp->flags = private ? RTPRIVATE : 0;
  380.         }
  381.     }
  382.     /* Check to see if this created an encapsulation loop */
  383.     gwtmp = gateway;
  384.  
  385.     for(;;){
  386.         if((rptmp = rt_lookup(gwtmp)) == NULLROUTE) {
  387.             break;                    /* No route to gateway, so no loop */
  388.         }
  389.         if(rptmp->iface != &Encap) {
  390.             break;                    /* Non-encap interface, so no loop */
  391.         }
  392.         if(rptmp == rp) {
  393.             rt_drop(target,bits);    /* Definite loop */
  394.             return NULLROUTE;
  395.         }
  396.         if(rptmp->gateway != 0) {
  397.             gwtmp = rptmp->gateway;
  398.         }
  399.     }
  400.     /* Set the timer field */
  401.     rp->timer.func = rt_timeout;
  402.     rp->timer.arg = rp;
  403.     set_timer(&rp->timer,ttl * 1000L);
  404.     stop_timer(&rp->timer);
  405.  
  406.     if(rp->metric > 1) {
  407.         /* start the timer if appropriate */
  408.         start_timer(&rp->timer);
  409.     }
  410.     return rp;
  411. }
  412.  
  413. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  414.  * if entry was not in table.
  415.  */
  416. int
  417. rt_drop(int32 target,unsigned int bits)
  418. {
  419.     struct route *rp, *rplast = NULLROUTE;
  420.  
  421.     if(bits == 0) {
  422.         /* Nail the default entry */
  423.         stop_timer(&R_default.timer);
  424.         R_default.iface = NULLIF;
  425.         return 0;
  426.     }
  427.     if(bits > 32) {
  428.         bits = 32;
  429.     }
  430.     /* Mask off target according to width */
  431.     target &= ~0L << (32 - bits);
  432.  
  433.     /* Search appropriate chain for existing entry */
  434.     for(rp = Routes; rp != NULLROUTE; rplast = rp, rp = rp->next) {
  435.         if(rp->target == target) {
  436.             break;
  437.         }
  438.     }
  439.     if(rp == NULLROUTE) {
  440.         return -1;    /* Not in table */
  441.     }
  442.     if(rplast != NULLROUTE) {
  443.         rplast->next = rp->next;
  444.     } else {
  445.         Routes = rp->next;
  446.     }
  447.     stop_timer(&rp->timer);
  448.  
  449.     xfree(rp);
  450.     return 0;
  451. }
  452.  
  453. #ifndef    GWONLY
  454. /* Given an IP address, return the MTU of the local interface used to
  455.  * reach that destination. This is used by TCP to avoid local fragmentation
  456.  */
  457. int16
  458. ip_mtu(int32 addr)
  459. {
  460.     struct route *rp;
  461.  
  462.     if((rp = rt_lookup(addr)) != NULLROUTE && rp->iface != NULLIF) {
  463.         if(rp->iface->forw != NULLIF) {
  464.             return rp->iface->forw->mtu;
  465.         } else {
  466.             return rp->iface->mtu;
  467.         }
  468.     }
  469.     return 0;
  470. }
  471.  
  472. /* Given a destination address, return the IP address of the local
  473.  * interface that will be used to reach it. If there is no route
  474.  * to the destination, pick the first non-loopback address.
  475.  */
  476. int32
  477. locaddr(int32 addr)
  478. {
  479.     struct route *rp;
  480.     struct iface *ifp;
  481.  
  482.     if(ismyaddr(addr) != NULLIF) {
  483.         return addr;    /* Loopback case */
  484.     }
  485.     if((rp = rt_lookup(addr)) != NULLROUTE && rp->iface != NULLIF) {
  486.         ifp = rp->iface;
  487.     } else {
  488.         for(ifp = Ifaces; ifp != NULLIF; ifp = ifp->next) {
  489.             if(ifp != &Loopback) {
  490.                 break;
  491.             }
  492.         }
  493.     }
  494.     if(ifp == NULLIF || ifp == &Loopback) {
  495.         return 0;    /* No dice */
  496.     }
  497.     if(ifp == &Encap){
  498.         /* Recursive call - we assume that there are no circular
  499.          * encapsulation references in the routing table!!
  500.          * (There is a check at the end of rt_add() that goes to
  501.          * great pains to ensure this.)
  502.          */
  503.         if(Encap.addr != 0) {
  504.             return Encap.addr;
  505.         }
  506.         return locaddr(rp->gateway);
  507.     }
  508.     return (ifp->forw == NULLIF) ? ifp->addr : ifp->forw->addr;
  509. }
  510. #endif
  511.  
  512. /* Look up target in hash table, matching the entry having the largest number
  513.  * of leading bits in common. Return default route if not found;
  514.  * if default route not set, return NULLROUTE
  515.  */
  516. struct route *
  517. rt_lookup(int32 target)
  518. {
  519.     struct route *rp, *rplast;
  520.     int bits;
  521.     int32 mask = ~0, tsave = target;            /* All ones in 'mask' */
  522.  
  523.     if(tsave == Ip_addr) {
  524.         return NULLROUTE;
  525.     }
  526.     for(bits = 31; bits >= 0; bits--) {
  527.         tsave &= mask;
  528.         rplast = NULLROUTE;
  529.  
  530.         for(rp = Routes; rp != NULLROUTE; rplast = rp, rp = rp->next) {
  531.             if(rp->target == tsave) {
  532.                 if(rplast != NULLROUTE) {
  533.                     /* Move to top of list */
  534.                     rplast->next = rp->next;
  535.                     rp->next = Routes;
  536.                     Routes = rp;
  537.                 }
  538.                 return rp;
  539.             }
  540.         }
  541.         mask <<= 1;
  542.     }
  543.     if(R_default.iface != NULLIF) {
  544.         return &R_default;
  545.     }
  546.     return NULLROUTE;
  547. }
  548.  
  549. /* Search routing table for entry with specific width */
  550. struct route *
  551. rt_blookup(int32 target,unsigned int bits)
  552. {
  553.     if(bits == 0 && R_default.iface != NULLIF) {
  554.         return &R_default;
  555.     } else {
  556.         struct route *rp;
  557.  
  558.         /* Mask off target according to width */
  559.         int32 tsave = target & (~0L << (32 - bits));
  560.  
  561.         for(rp = Routes; rp != NULLROUTE; rp = rp->next) {
  562.             if(rp->target == tsave) {
  563.                 return rp;
  564.             }
  565.         }
  566.     }
  567.     return NULLROUTE;
  568. }
  569.  
  570. #ifdef XXX
  571. /* Scan the routing table. For each entry, see if there's a less-specific
  572.  * one that points to the same interface and gateway. If so, delete
  573.  * the more specific entry, since it is redundant.
  574.  */
  575. static void
  576. rt_merge(int trace)
  577. {
  578.     int bits, j;
  579.     struct route *rp, *rpnext, *rp1;
  580.  
  581.     for(bits = 32; bits > 0; bits--) {
  582.         for(rp = Routes; rp != NULLROUTE; rp = rpnext) {
  583.             rpnext = rp->next;
  584.             for(j = bits-1; j >= 0; j--) {
  585.                 if((rp1 = rt_blookup(rp->target,j)) != NULLROUTE
  586.                  && rp1->iface == rp->iface
  587.                  && rp1->gateway == rp->gateway){
  588.                     if(trace > 1)
  589.                         tprintf("merge %s %d\n",
  590.                          inet_ntoa(rp->target),
  591.                          rp->bits);
  592.                     rt_drop(rp->target,rp->bits);
  593.                     break;
  594.                 }
  595.             }
  596.         }
  597.     }
  598. }
  599. #endif
  600.